package com.summer.study.leetcode.algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @auther: 杨杰
 * @date: 2019/7/29 09:50
 * @description: 有效的括号
 * https://leetcode-cn.com/problems/valid-parentheses
 */
public class valid_parentheses_20 {


    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char item : s.toCharArray()) {
            if (item == '(') stack.push(')');
            else if (item == '[') stack.push(']');
            else if (item == '{') stack.push('}');
            else if (stack.isEmpty() || stack.pop() != item) return false;
        }
        return stack.isEmpty();

    }


    public static void main(String[] args) {
        System.out.println(isValid2("{[]}"));
    }


    public static boolean isValid2(String s) {
        Map<Character, Character> map = new HashMap<>();

        map.put('}', '{');
        map.put(']', '[');
        map.put(')', '(');
        Stack<Character> stack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            char item = s.charAt(i);
            //不是右括号，是左括号，压入栈底
            if (!map.containsKey(item)) {
                stack.push(item);
            } else {
                //是右括号，判断栈底元素和自身是否匹配
                if (stack.empty() || (!stack.pop().equals(map.get(item)))) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }


}
